1. 质数：
（1）质数的判定：
	试除法：
	bool is_prime(int n){
		if(n<2) return false;
		for(int i=2;i<n;i++)
			if(n%i==0)
					return false;
		return true;
	上面的时间复杂度为o(n)的吗，很暴力
	我们对着上面的式子进行优化，结合质数的性质，质数都是成对出现的。所以我们只需要列出最小的一个就可以了
	假设d为其中一个，n/d就是另外一个  d<n/d  d<根号（n）
	所以改成for(int i=2;i<sqrt(n);i++)  但是不推荐，因为sqrt很慢；
	推荐 for(int i=2;i<n/i;i++)
（2）分解质因数
	试除法：从小到大列举我们的质因数
	void divide(int n){
		for(int i=2;i<=n;i++)
			if(n%i==0){
				int s=0;
				while(n%i==0){
					n/=i;
					s++;
				}
				printf("%d %d\n",i,s);
			}
	}
	以上的过程看视就是把我们的每一个数列举出来而不是质因数，但是这儿有一点就是我们
	当列举到i的时候，已经把我们的2---i所有的数已经列举了，所以i一定是质数；
	举个例子 当i=6 的时候，能够满足if(n%i==0)条件的n数一定都被i=2,3 磨干净了
	----------------------------------
	那么我们参考上面找质数的方法进行优化呢？  参考性质  一个数最多含有一个大于qort(n)的质因数，证明用反证法；
	所以：
	void divide(int n){
		for(int i=2;i<=n/i;i++)
			if(n%i==0){
				int s=0;
				while(n%i==0){
					n/=i;
					s++;
				}
				printf("%d %d\n",i,s);
			}
		if(n>1) printf("%d %d\n",n,1); //我们将这个大于qort(n)的数放在了最后面来处理；
	}
（3） 筛质数
朴素筛法：o(nlogn)
	int primes[N], cnt;     // primes[]存储所有素数
	bool st[N];         // st[x]存储x是否被筛掉
	void get_primes(int n)
	{
		for (int i = 2; i <= n; i ++ )000
		{
			if (!st[i]) primes[cnt ++ ] = i;
			for (int j = i + i; j <= n; j += i)  //为什么找一个数的倍数的标准做法
				st[j] = true;
		}
	}
	以上其实没有必要把每一个数的倍数都来筛一遍，我们只需要例举出质数的倍数就可以了
----------------
埃式筛法：o(nloglogn);
	int primes[N], cnt;     // primes[]存储所有素数
	bool st[N];         // st[x]存储x是否被筛掉
	void get_primes(int n)
	{
		for (int i = 2; i <= n; i ++ )
		{
			if (st[i]) continue;
			primes[cnt ++ ] = n; 
			for (int j = i + i; j <= n; j += i)
				st[j] = true;
		}
	}
---------
线性筛法：o(n)
	int primes[N], cnt;     // primes[]存储所有素数
	bool st[N];         // st[x]存储x是否被筛掉
	void get_primes(int n)
	{
		for (int i = 2; i <= n; i ++ )
		{
			if (!st[i]) primes[cnt ++ ] = i; 
			for (int j = 0; primes[j] <= n / i; j ++ )
			{
				st[primes[j] * i] = true;
				if (i % primes[j] == 0) break;// primes[j]一定是i的最小质因子  
			}
		}
	}
	1. 当i为质数的时候，i就是primes中最大的质数。那么当所以primes[j]肯定是primes[j]*i最小的质数。
		依次轮询就可以了。
	2. 当i为合数的时候，前期和上面一样慢慢的轮询，等到i%primes[j]==0 的时候就必须要break了，不然
		后面的primes[j] * i就是虚假的，因为i其实背后还有一个primes[j-1]更小的质数。
	3. 证明（我们假设i为合数，因为质数的时候很简单） ：当i%primes[j]!=0 的时候，由于我们prime是从从小往大取的，所以prime[j]一定是最小的质数（比i的最小质因数还小），primes[j]肯定是primes[j]*i最小的质数。
	3. 证明（我们假设i为合数，因为质数的时候很简单） ：当i%primes[j]!=0 的时候，由于我们prime是从从小往大取的，所以prime[j]一定是最小的质数（比i的最小质因数还小），primes[j]肯定是primes[j]*i最小的质数。
		当i%primes[j]==0 的时候，prime[j]一定是i的最小质因数。所以也是primes[j]*i最小的质数。
----------------------------------


1. 约数：  一个数的约数最多也就1500--1600 个
（1）试除法求一个数的所有约数
	枚举两个约束中比较小的一个
	vector<int> get_divisors(int x)   O(sqrt(n));
	{
		vector<int> res;
		for (int i = 1; i <= x / i; i ++ )
			if (x % i == 0)
			{
				res.push_back(i);
				if (i != x / i) res.push_back(x / i);  //如刚好是平方智慧重复存
			}
		sort(res.begin(), res.end());
		return res;
	}
（2）约数的个数 
（3）约束的之和
	如果 N = p1^c1 * p2^c2 * ... *pk^ck
	约数个数： (c1 + 1) * (c2 + 1) * ... * (ck + 1)
	约数之和： (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)
------
个数：
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 110, mod = 1e9 + 7;
int main()
{
    int n;
    cin >> n;

    unordered_map<int, int> primes;

    while (n -- )
    {
        int x;
        cin >> x;

        for (int i = 2; i <= x / i; i ++ )
            while (x % i == 0)
            {
                x /= i;
                primes[i] ++ ;
            }

        if (x > 1) primes[x] ++ ;
    }

    LL res = 1;
    for (auto p : primes) res = res * (p.second + 1) % mod;

    cout << res << endl;

    return 0;
}
-----------
求和：
    LL res = 1;
    for (auto p : primes)
    {
        LL a = p.first, b = p.second;
        LL t = 1;
        while (b -- ) t = (t * a + 1) % mod;
        res = res * t % mod;
    }
-----------
（4）欧几里得算法 ---求最大公约数---辗转相除法
定理：假设c为(a,b)的最大公约数 那么c也是（b,a%b)的最大公约束；
		因为a%b== a-(a/b)*b ==a-k*b;
	int gcd(int a, int b)
	{
		return b ? gcd(b, a % b) : a;
	}
-----------


3. 欧拉函数
	1-n中和n互质数的个数 （互质：只有公约数1的两个数）  也就是最大公约数为1-----（c,m)=1;
	如果 N = p1^c1 * p2^c2 * ... *pk^ck
	我们去掉1-n中所有p1,p2,...pk的倍数
	-------------------------容斥原理----------------------------
	|那么有多少个呢？N-N/p1-N/p2-N/p3....N/pk;这里面有多去的部分|
	|加上所有pi*pj的倍数  +N/(Pi*pj)+...						|
	|减去所有pi*pj*pk的倍数 									|
	-------------------------------------------------------------
	那么互质的个数=N*(1-1/p1)*(1-1/p2)*.....(1-1/pk);  时间复杂度瓶颈在分解质因数上面
	---------------------------------------------------------------------------------
	int phi(int x)
	{
		int res = x;
		for (int i = 2; i <= x / i; i ++ )
			if (x % i == 0)
			{
				res = res / i * (i - 1);  //为什么不写成  res=res*(1-1/i) ??挺重要的，这样改写（避免产生小数）
				while (x % i == 0) x /= i;
			}
		if (x > 1) res = res / x * (x - 1);

		return res;
	}
----------		
筛法的欧拉函数：求的是每一个数的欧拉函数（利用了线性的筛法进行推导的）
	int primes[N], cnt;     // primes[]存储所有素数
	int euler[N];           // 存储每个数的欧拉函数
	bool st[N];         // st[x]存储x是否被筛掉
	void get_eulers(int n)
	{
		euler[1] = 1;
		for (int i = 2; i <= n; i ++ )
		{
			if (!st[i])
			{
				primes[cnt ++ ] = i;
				euler[i] = i - 1;   //当是一个质数的时候，欧拉就是i-1
			}
			for (int j = 0; primes[j] <= n / i; j ++ )
			{
				int t = primes[j] * i;
				st[t] = true;
				if (i % primes[j] == 0)
				{
					euler[t] = euler[i] * primes[j];//==0的时候
					break;
				}
				euler[t] = euler[i] * (primes[j] - 1);//！=0的时候
			}
		}
	}
---------------
858993459
4. 快速幂
	思想：反复平方法
		求 a^k mod p，时间复杂度 O(logk)。
	int qmi(int a, int k, int p)
	{
		int res = 1 % p, t = a;
		while (k)
		{
			if (k&1) res = (long long)res * t % p; //防止数值太大越界
			t = (long long)t * t % p;
			k >>= 1;
		}
		return res;
	}
------------

5 扩展欧几里得定理
	裴蜀定理： 有一对正整数a,b,那么一定存在非零整数x,y，使得ax+by=最大公约数(a,b);
	 // 求x, y，使得ax + by = gcd(a, b)
	int exgcd(int a, int b, int &x, int &y)
	{
		if (!b)
		{
			x = 1; y = 0;
			return a;
		}
		int d = exgcd(b, a % b, y, x);
		y -= (a/b) * x;
		return d;
	}
   
6. 中国剩余定理
	不用掌握 了解即可

7. 高斯消元法
（1）求解多元线性方程组
	// a[N][N]是增广矩阵
	int gauss()
	{
		int c, r;
		for (c = 0, r = 0; c < n; c ++ )
		{
			int t = r;
			for (int i = r; i < n; i ++ )   // 找到绝对值最大的行
				if (fabs(a[i][c]) > fabs(a[t][c]))
					t = i;

			if (fabs(a[t][c]) < eps) continue;

			for (int i = c; i <= n; i ++ ) swap(a[t][i], a[r][i]);      // 将绝对值最大的行换到最顶端
			for (int i = n; i >= c; i -- ) a[r][i] /= a[r][c];      // 将当前上的首位变成1
			for (int i = r + 1; i < n; i ++ )       // 用当前行将下面所有的列消成0
				if (fabs(a[i][c]) > eps)
					for (int j = n; j >= c; j -- )
						a[i][j] -= a[r][j] * a[i][c];

			r ++ ;
		}

		if (r < n)
		{
			for (int i = r; i < n; i ++ )
				if (fabs(a[i][n]) > eps)
					return 2; // 无解
			return 1; // 有无穷多组解
		}

		for (int i = n - 1; i >= 0; i -- )
			for (int j = i + 1; j < n; j ++ )
				a[i][n] -= a[i][j] * a[j][n];

		return 0; // 有唯一解
	}

8. 求组合数
（1）几种方案中选择几种方案 
	10w组询问   0<a，b<2000  用递推的方法 O(n^2)
	// c[a][b] 表示从a个苹果中选b个的方案数
	for (int i = 0; i < N; i ++ )
		for (int j = 0; j <= i; j ++ )
			if (!j) c[i][j] = 1;
			else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
------------
（2）用预处理的方法  O(NlogN)
	1w 组询问  1<b<a<10^5
	首先预处理出所有阶乘取模的余数fact[N]，以及所有阶乘取模的逆元infact[N]
	如果取模的数是质数，可以用费马定理求逆元
	int qmi(int a, int k, int p)    // 快速幂模板
	{
		int res = 1;
		while (k)
		{
			if (k & 1) res = (LL)res * a % p;
			a = (LL)a * a % p;
			k >>= 1;
		}
		return res;
	}

	// 预处理阶乘的余数和阶乘逆元的余数
	fact[0] = infact[0] = 1;
	for (int i = 1; i < N; i ++ )
	{
		fact[i] = (LL)fact[i - 1] * i % mod;
		infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
	}
（3）只有20组询问，但是询问的范围暴大
	20 组询问  1<b<a<10^18  
	lucas定理  o(plognlogp)
	若p是质数，则对于任意整数 1 <= m <= n，有：
    C(n, m) = C(n % p, m % p) * C(n / p, m / p) (mod p)
	int qmi(int a, int k)       // 快速幂模板
	{
		int res = 1;
		while (k)
		{
			if (k & 1) res = (LL)res * a % p;
			a = (LL)a * a % p;
			k >>= 1;
		}
		return res;
	}


	int C(int a, int b)     // 通过定理求组合数C(a, b)
	{
		int res = 1;
		for (int i = 1, j = a; i <= b; i ++, j -- )
		{
			res = (LL)res * j % p;
			res = (LL)res * qmi(i, p - 2) % p;
		}
		return res;
	}


	int lucas(LL a, LL b)
	{
		if (a < p && b < p) return C(a, b);
		return (LL)C(a % p, b % p) * lucas(a / p, b / p) % p;
	}
----------------
（4）直接求组合数，组合数很大，不能磨
	当我们需要求出组合数的真实值，而非对某个数的余数时，分解质因数的方式比较好用：
    1. 筛法求出范围内的所有质数
    2. 通过 C(a, b) = a! / b! / (a - b)! 这个公式求出每个质因子的次数。 n! 中p的次数是 n / p + n / p^2 + n / p^3 + ...
    3. 用高精度乘法将所有质因子相乘
	int primes[N], cnt;     // 存储所有质数
	int sum[N];     // 存储每个质数的次数
	bool st[N];     // 存储每个数是否已被筛掉
	void get_primes(int n)      // 线性筛法求素数
	{
		for (int i = 2; i <= n; i ++ )
		{
			if (!st[i]) primes[cnt ++ ] = i;
			for (int j = 0; primes[j] <= n / i; j ++ )
			{
				st[primes[j] * i] = true;
				if (i % primes[j] == 0) break;
			}
		}
	}

	int get(int n, int p)       // 求n！中的次数
	{
		int res = 0;
		while (n)
		{
			res += n / p;
			n /= p;
		}
		return res;
	}

	vector<int> mul(vector<int> a, int b)       // 高精度乘低精度模板
	{
		vector<int> c;
		int t = 0;
		for (int i = 0; i < a.size(); i ++ )
		{
			t += a[i] * b;
			c.push_back(t % 10);
			t /= 10;
		}

		while (t)
		{
			c.push_back(t % 10);
			t /= 10;
		}

		return c;
	}

	get_primes(a);  // 预处理范围内的所有质数

	for (int i = 0; i < cnt; i ++ )     // 求每个质因数的次数
	{
		int p = primes[i];
		sum[i] = get(a, p) - get(b, p) - get(a - b, p);
	}

	vector<int> res;

	for (int i = 0; i < cnt; i ++ )     // 用高精度乘法将所有质因子相乘
		for (int j = 0; j < sum[i]; j ++ )
			res = mul(res, primes[i]);
--------------------------------
（5） 卡特兰数：
	给定n个0和n个1，它们按照某种顺序排成长度为2n的序列，满足任意前缀中0的个数都不少于1的个数的序列的数量为：
	Cat(n) = C(2n, n) / (n + 1)
	
9. 容斥原理
	同上面的公式一样：
	-------------------------容斥原理----------------------------
	|假如我们要去除1-n中 p1，p2,p3，p4,p5....的倍数				|
	|那么有多少个呢？N-N/p1-N/p2-N/p3....N/pk;这里面有多去的部分|
	|加上所有pi*pj的倍数  +N/(Pi*pj)+...						|
	|减去所有pi*pj*pk的倍数 									|
	-------------------------------------------------------------
	我们现在只是分析一下这个复杂度，首先就是有多少中可能
	S1 U S2 U S3 =(S1+S2+S3)-S1∩S2-S2∩S3-S1∩S3+S1∩S2∩S3
	也就是S1、S2、S3中选1个，选2个，选3个组合在一起，也就是在3个中选择任意多个的可能性组合
	那么再抽象就是S1 S2 S3分别选和不选 也就是2^n-1 种选择的可能性；
	那么一般可以用移位操作来表示选和不选:1-(2^3-1) 也就是 001+010+100-011-101-110+111 这几种选择
	我们就以通过"位"来表示这几种容斥的情况，其中我们在操作的时候还要记下1个数，1为奇数为+，1为偶数则为-；
	------
10. Nim游戏：
	简单的Nim游戏就是看我们的选择的情况为任意多个还是限定的个
	如果是任意多个那么其实我们的sg(n)=n;
	所以我们的sg(n1)^sg(n2)^sg(n3)^sg(n4)^sg(n5)^sg(n6)=n1^n2^n3^n4^n5^n6;
	那么结论就是：sg(n1)^sg(n2)^sg(n3)^sg(n4)^sg(n5)^sg(n6)>0 先手的那么我们就必赢
				  sg(n1)^sg(n2)^sg(n3)^sg(n4)^sg(n5)^sg(n6)=0 先手的那么我们就必输
	
	那么结果是怎样证明的呢？
	我们直接用n1^n2^n3^n4^n5^n6操作而不用sg（），实际上我们应该用sg来操作；
	假设：n1^n2^n3^n4^n5^n6=x 为必胜态，那么先手的我就一定能转换成必输态
		  x的最高位有一个1，假设我们是n6赋予他的；那么n6^x<x;
		  所以我们就可以把n6改变成n6^x;(变成比自己小的没有问题吧)因为我们sg(n)代表的就是最小的一个不在可能集合里面的数；
		那么n1^n2^n3^n4^n5^n6^x=x^x=0; 那么就转换成为必输态；
			相同必输态只要操作，就会变为必赢态。
	
-------------------------------------------------------
	一个局面的sg的值--->被划分成了两个局面--->
	那么sg(b1,b2)=sg(b1)^sg(b2)
		sg(c1,c2)=sg(c1)^sg(c2)
		sg(d1,d2)=sg(d1)^sg(d2)
		那么sg(a)=mex(sg(b1,b2),sg(c1,c2),sg(d1,d2));
-------------------------------------------------------
	
	
	
	
	
	
	
	